Batch 3 - Class 132 - Invariants

• Solve for (TWO)^2 = THREE
• 138 ^ 2 = 19044  (tough)

• Play the game with kids - allow them to start with 6 zeros and 5 ones. At any step, they can remove two numbers and replace it with one. If they remove the same numbers, they put a zero there, and if they replace different numbers, they put a one there. At end of 10 steps, tell them that you can guess what they are left with - its a one.
• If you play for 3 or 4 times, kids should get what's going on. See if they can come up with notion of "Invariant"
• If not, ask them what is staying constant across steps
• Essentially, its always an odd number of 1s and hence last number has to be 1
• Ask them what would happen if we started with 23 zeros and 15 ones - and other combinations like that
• We have a language composed of two letters A and O. Further insertion of AO neighboring letters, or deletion of OA and AAOO doesn't change the meaning of the words. Can you be sure that AOO and OAA have the same meaning?
• Answer: Note that any insertion of deletion doesn't change the (number of Os - number of As) - since you are starting with different number of those (-1 versus 1), we can't be sure they are the same.
• Articulate an idea of Invariant - you start with something and are allowed to do certain operations to get to another state. At each step, "something" doesn't change, and that "something" forms the basis of equivalence. 
• There are six sectors of a disc, with a pawn in each sector. At each step, you take two pawns and move them each to any of the adjacent sectors. Can you get all pawns in the same sector?

• Answer: If you number the six sectors 1..6 in order, then at each step the odd/even parity remains the same. Starting sum is 21, i.e. odd. Getting all six pawns in same sector requires even parity. Hence it is not possible.
• There are six sparrows sitting on six trees in a row, each 10 meters apart. At each step, a sparrow flies from a tree to another, and another sparrow flies the same distance in opposite direction. Can all the sparrows get on the same tree?
• Answer: No. Since counting distance from first tree, average distance is 25 meters. Total distance is invariant, and there is no tree at 25 meter distance
• Can they get on the same tree if there are 7 sparrows and 7 trees

  Answer: Yes. On the middle tree

• Play a game where the kids start with numbers 1 to 20 on the board. At each step, you erase two numbers and then replace those with a+b-1. Let them do this for 19 steps, and guess the final number as 191. Ask the kids to figure out what's happened
• Answer: The order of choosing numbers is unimportant. The final number is sum of all numbers - number of steps. So 210 - 19 = 191
• What is the invariant?

  Answer: Sum of all numbers - number of numbers (with 20 numbers it is 191, but at the end as well it is 191, and since there is only one number, the number must be 190)